
/**
 * 堆排序
 * @param arr 
 */
export const heapSort = (arr: number[]) => {
    /**
    * 交换元素位置
    * @param l 
    * @param r 
    */
    const swap = (l: number, r: number) => {
        const tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp
    }

    /**
     * 获取左子节点的索引
     * @param i 
     */
    const getLeftChild = (i: number) => {
        return ((i + 1) << 1) - 1
    }

    /**
     * 获取右子节点的索引
     * @param i 
     */
    const getRightChild = (i: number) => {
        return (i + 1) << 1
    }

    /**
     * 获取左右中的最大值
     * @param l 
     * @param r 
     */
    const getMax = (l: number, r: number) => {
        let ld = arr[l]
        let rd = arr[r];
        // 右边没有孩子的 或者是 r 大于等于了sizes(越界了) ，返回左边
        if (rd == undefined || r >= sizes) return l
        const i = ld > rd ? l : r
        return i
    }

    /**
     * 下滤
     * @param index 
     */
    const down = (i = 0) => {
        // 从i开始往下下滤

        // 获取非叶子节点的数量, 下滤只要处理非叶子节点
        const half = sizes >> 1;
        // debugger
        // 直到i 等于 half
        while (i < half) {
            // 获取左右子节点的数量
            let lI = getLeftChild(i),
                rI = getRightChild(i);

            // 获取左右子节点中最大的
            const maxI = getMax(lI, rI);

            // 最顶的都大于左右中最大的，直接返回即可
            if (getMax(maxI, i) === i) {
                break;
            }

            // 交换位置
            swap(maxI, i)


            // 更改i
            i = maxI;

        }

    }

    // 数组的长度
    let sizes = arr.length;


    // 批量建堆 （从非叶子节点最后一个开始往前）
    let len = (sizes >> 1) - 1
    for (; len >= 0; len--) {
        down(len)
    }


    /**
        [63, 57, 69, 12, 37, 6, 88, 91, 93, 100]
        sizes = 0 => 对上面进行下溢
     */

    // 直到sizes小于等于1
    while (sizes > 1) {
        // 交换最后一个元素(还没是最大的元素)和第一个元素 (第一个元素是最大值)
        let s = --sizes;
        swap(0, s)
        // 对0位置做下滤处理
        // debugger
        down()
    }
}


